From 5321a583c17a0d910face8e008ece7fef9273c59 Mon Sep 17 00:00:00 2001 From: oliskoli Date: Tue, 1 Apr 2008 18:07:33 +0000 Subject: [PATCH] avltree: Initial checkin. git-svn-id: http://gpsbabel.googlecode.com/svn/trunk@3156 f51c46e8-681c-474f-0cfe-069cfd0219fb --- gpsbabel/Makefile.in | 3 +- gpsbabel/avltree.c | 723 +++++++++++++++++++++++++++++++++++++++++++ gpsbabel/avltree.h | 94 ++++++ 3 files changed, 819 insertions(+), 1 deletion(-) create mode 100644 gpsbabel/avltree.c create mode 100644 gpsbabel/avltree.h diff --git a/gpsbabel/Makefile.in b/gpsbabel/Makefile.in index 1ee90f9cb..452deef86 100644 --- a/gpsbabel/Makefile.in +++ b/gpsbabel/Makefile.in @@ -90,7 +90,7 @@ LIBOBJS = queue.o route.o waypt.o filter_vecs.o util.o vecs.o mkshort.o \ csv_util.o strptime.o grtcirc.o vmem.o util_crc.o xmlgeneric.o \ uuid.o formspec.o xmltag.o cet.o cet_util.o fatal.o rgbcolors.o \ inifile.o garmin_fs.o gbsleep.o units.o @GBSER@ gbser.o \ - gbfile.o parse.o \ + gbfile.o parse.o avltree.o \ $(PALM_DB) $(GARMIN) $(JEEPS) $(SHAPE) @ZLIB@ $(FMTS) $(FILTERS) OBJS = main.o globals.o $(LIBOBJS) @FILEINFO@ @@ -345,6 +345,7 @@ an1.o: an1.c defs.h config.h queue.h gbtypes.h zlib/zlib.h zlib/zconf.h \ gbfile.h cet.h cet_util.h inifile.h an1sym.h arcdist.o: arcdist.c defs.h config.h queue.h gbtypes.h zlib/zlib.h \ zlib/zconf.h gbfile.h cet.h cet_util.h inifile.h filterdefs.h grtcirc.h +avltree.o: avltree.h avltree.c defs.h gbtypes.h config.h axim_gpb.o: axim_gpb.c defs.h config.h queue.h gbtypes.h zlib/zlib.h \ zlib/zconf.h gbfile.h cet.h cet_util.h inifile.h bcr.o: bcr.c defs.h config.h queue.h gbtypes.h zlib/zlib.h zlib/zconf.h \ diff --git a/gpsbabel/avltree.c b/gpsbabel/avltree.c new file mode 100644 index 000000000..ca242be58 --- /dev/null +++ b/gpsbabel/avltree.c @@ -0,0 +1,723 @@ +/* + + AVL tree implementation. + + Copyright (C) 2008 Olaf Klein, o.b.klein@gpsbabel.org + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA + +*/ + +#include "avltree.h" + +#define MYNAME "avltree" + +#ifdef DEBUG_MEM +# define AVLTREE_MAGIC 0x41564c53 +/* ((((((0L | 'A') << 8) | 'V') << 8) | 'L') << 8) | 'T'; */ +#endif + +#ifdef MEM_DEBUG +void avltree_check_handle(const void *tree); +#endif +static void avltree_node_free(const avltree_t *tree, avlnode_t *node); +static int avltree_node_height(avlnode_t *node); +static int avltree_insert_node(avltree_t *tree, avlnode_t **root, const char *key, const void *data); +static int avltree_delete_node(avltree_t *tree, const char *key, avlnode_t **root, int *changed); +static avlnode_t *avltree_right_rotation(avlnode_t *A); +static avlnode_t *avltree_left_rotation(avlnode_t *A); +static avlnode_t *avltree_left_right_rotation(avlnode_t *A); +static avlnode_t *avltree_right_left_rotation(avlnode_t *A); +static avlnode_t *avltree_dupe_node(const avltree_t *tree, const avlnode_t *node); +static int avltree_strcmpr(const char *s1, const char *s2); +static int avltree_case_ignore_strcmpr(const char *s1, const char *s2); +static avlnode_t *avltree_find_next(const avltree_t *tree, avlnode_t *node, const char *key); +static void avltree_save_key(avltree_t *tree, const char *key); + + +#ifdef MEM_DEBUG +# define AVLTREE_CHECK_HANDLE(a) avltree_valid_tree(a) +#else +# define AVLTREE_CHECK_HANDLE(a) +#endif + +#define AVLTREE_INVALID_BALANCE "%s/%s.%d: Invalid balance %d at node \"%s\"!\n", \ + tree->module, MYNAME, __LINE__, node->balance, node->key + + +/* Allocate and initialize an AVL Tree */ + +avltree_t * +avltree_init(const int options, const char *module) +{ + avltree_t *tree; + + if ((module == NULL) || (*module == '\0')) + fatal(MYNAME ": 'avltree_init' should be called with a valid module name!\n"); + + tree = xcalloc(1, sizeof(*tree)); + tree->options = options; + tree->module = module; + + if (options & AVLTREE_NON_CASE_SENSITIVE) { + if (options & AVLTREE_DESCENDING) + tree->compare = avltree_case_ignore_strcmpr; /* descending, non-case-sensitive */ + else + tree->compare = case_ignore_strcmp; /* ascending, non-case-sensitive */ + } + else { + if (options & AVLTREE_DESCENDING) + tree->compare = avltree_strcmpr; /* descending, case-sensitive */ + else + tree->compare = strcmp; /* ascending, case-sensitive */ + } + + return tree; +} + + +/* Destroy an AVL Tree */ + +void +avltree_done(avltree_t *tree) +{ + AVLTREE_CHECK_HANDLE(tree); + + avltree_save_key(tree, NULL); + if (tree->count) + avltree_node_free(tree, tree->root); + xfree(tree); +} + + +/* Get number of items in tree */ + +int +avltree_count(const avltree_t *tree) +{ + AVLTREE_CHECK_HANDLE(tree); + + return tree->count; +} + + +/* Delete item with key [key] */ + +int +avltree_delete(avltree_t *tree, const char *key) +{ + int changed = 0; + + AVLTREE_CHECK_HANDLE(tree); + + if (key == NULL) + fatal("%s/%s.%d: Attempt to delete a NULL-pointer!\n", + tree->module, MYNAME, __LINE__); + + return avltree_delete_node(tree, key, &tree->root, &changed); +} + + +/* Duplicate an existing tree */ + +avltree_t * +avltree_dupe(const avltree_t *tree, const char *module) +{ + avltree_t *dupe; + + AVLTREE_CHECK_HANDLE(tree); + + dupe = avltree_init(tree->options, module); + if ((dupe->count = tree->count)) + dupe->root = avltree_dupe_node(tree, tree->root); + + return dupe; +} + + +/* Find key [key] in tree */ + +int +avltree_find(const avltree_t *tree, const char *key, const void **data) +{ + avlnode_t *node; + + AVLTREE_CHECK_HANDLE(tree); + + node = tree->root; + while (node) { + int compare = tree->compare(key, node->key); + + if (compare < 0) + node = node->left; + else if (compare > 0) + node = node->right; + else { + if (data) + (*data) = node->data; + break; + } + } + + return (node) ? 1 : 0; +} + + +/* Get the first (the MIN-) entry of the tree */ + +const char * +avltree_first(const avltree_t *tree, const void **data) +{ + return avltree_next(tree, NULL, data); +} + + +/* Get the current height of the tree */ + +int +avltree_height(const avltree_t *tree) +{ + AVLTREE_CHECK_HANDLE(tree); + + if (tree->count) + return avltree_node_height(tree->root); + else + return 0; +} + + +/* Insert key [key] and [data] into tree */ + +int +avltree_insert(avltree_t *tree, const char *key, const void *data) +{ + int count; + + AVLTREE_CHECK_HANDLE(tree); + + if (key == NULL) + fatal("%s/%s.%d: Attempt to insert a NULL-pointer!\n", + tree->module, MYNAME, __LINE__); + + count = tree->count; + avltree_insert_node(tree, &tree->root, key, data); + return (count != tree->count) ? 1 : 0; +} + + +/* Get the next (the entry above [key]) */ + +const char * +avltree_next(const avltree_t *tree, const char *key, const void **data) +{ + avlnode_t *node; + + AVLTREE_CHECK_HANDLE(tree); + + if (key == NULL) + fatal("%s/%s.%d: Attempt to look for a NULL-pointer!\n", + tree->module, MYNAME, __LINE__); + + node = tree->root; + if (! node) return NULL; + + if ((node = avltree_find_next(tree, node, key))) { + avltree_save_key((avltree_t *)tree, node->key); + if (data) + (*data) = node->data; + } + else + avltree_save_key((avltree_t *)tree, NULL); + + return tree->key; +} + + +/* ------------------------------ static stuff ------------------------------ */ + + +#ifdef MEM_DEBUG + +void +avltree_check_handle(const avltree_t *tree) +{ + if (! tree) + fatal(MYNAME ": Invalid (NULL-) pointer!\n"); + if (tree->magic != AVLTREE_MAGIC) + fatal(MYNAME ": Invalid (no AVL tree object) pointer!\n"); +} + +#endif + + +static void +avltree_node_free(const avltree_t *tree, avlnode_t *node) +{ + if ((! (tree->options & AVLTREE_STATIC_KEYS)) && node->key) + xfree((char *)node->key); + if (node->left) + avltree_node_free(tree, node->left); + if (node->right) + avltree_node_free(tree, node->right); + xfree(node); +} + + +static int +avltree_node_height(avlnode_t *node) +{ + int height = 1; + + if (node->balance < 0) + height += avltree_node_height(node->left); + else if (node->right) + height += avltree_node_height(node->right); + + return height; +} + + +static avlnode_t * +avltree_right_rotation(avlnode_t *A) +{ +/* +> A B +> / \ / \ +> \ / \ +> B -->> A . +> / \ / \ / \ +> \ +> . +> / \ +*/ + avlnode_t *B; + + B = A->right; + A->right = B->left; + B->left = A; + + /* update balance of all touched nodes */ + /* reference: */ + + B->balance--; + A->balance = -(B->balance); + + return B; +} + + +static avlnode_t * +avltree_left_rotation(avlnode_t *A) +{ +/* +> A B +> / \ / \ +> / / \ +> B -->> . A +> / \ / \ / \ +> / +> . +> / \ +*/ + avlnode_t *B; + + B = A->left; + A->left = B->right; + B->right = A; + + /* update balance of all touched nodes */ + /* reference: */ + + B->balance++; + A->balance = -(B->balance); + + return B; +} + + +static avlnode_t * +avltree_left_right_rotation(avlnode_t *A) +{ +/* +> A C +> / \ / \ +> / / \ +> B -->> B A +> / \ / \ / \ +> \ +> C +*/ + avlnode_t *B, *C; + + B = A->left; + C = B->right; + A->left = C->right; + B->right = C->left; + C->right = A; + C->left = B; + + /* update balance of all touched nodes */ + /* reference: */ + + A->balance = (C->balance > 0) ? 0 : -(C->balance); + B->balance = (C->balance < 0) ? 0 : -(C->balance); + C->balance = 0; + + return C; +} + + +static avlnode_t * +avltree_right_left_rotation(avlnode_t *A) +{ +/* +> A C +> / \ / \ +> \ / \ +> B -->> B A +> / \ / \ / \ +> / +> C +*/ + avlnode_t *B, *C; + + B = A->right; + C = B->left; + A->right = C->left; + B->left = C->right; + C->left = A; + C->right = B; + + /* update balance of all touched nodes */ + /* reference: */ + + A->balance = (C->balance < 0) ? 0 : -(C->balance); + B->balance = (C->balance > 0) ? 0 : -(C->balance); + C->balance = 0; + + return C; +} + + +static int +avltree_insert_node(avltree_t *tree, avlnode_t **root, const char *key, const void *data) +{ + int changed = 0; + int compare; + avlnode_t *node = (*root); + + if (node == NULL) { + (*root) = node = xcalloc(1, sizeof(*node)); + if (tree->options & AVLTREE_STATIC_KEYS) + node->key = key; + else + node->key = xstrdup(key); + node->data = data; + tree->count++; + return 1; /* anyway, our tree has been changed */ + } + + compare = tree->compare(key, node->key); + + if (compare < 0) { + if (avltree_insert_node(tree, &node->left, key, data)) { + changed = (--node->balance != 0); + switch(node->balance) { + case -2: + if (node->left->balance < 0) + node = avltree_left_rotation(node); + else + node = avltree_left_right_rotation(node); + (*root) = node; + case 0: + changed = 0; + case -1: + break; + default: + /* should be impossible :-) */ + fatal(AVLTREE_INVALID_BALANCE); + } + } + else + changed = 0; + } + else if (compare > 0) { + if (avltree_insert_node(tree, &node->right, key, data)) { + changed = (++node->balance != 0); + switch(node->balance) { + case +2: + if (node->right->balance > 0) + node = avltree_right_rotation(node); + else + node = avltree_right_left_rotation(node); + (*root) = node; + case 0: + changed = 0; + case +1: + break; + default: + /* should be impossible :-) */ + fatal(AVLTREE_INVALID_BALANCE); + } + } + else + changed = 0; + } + else { + if (tree->options & AVLTREE_PARANOIAC) + fatal("%s/%s.%d: Duplicate keys are not allowed (\"%s\")!\n", + tree->module, MYNAME, __LINE__, key); + changed = 0; + } + + return changed; +} + + + +static int +avltree_delete_node(avltree_t *tree, const char *key, avlnode_t **root, int *changed) +{ + avlnode_t *node = (*root); + int deleted = 0; + int compare; + + if (node == NULL) { + if (tree->options & AVLTREE_PARANOIAC) + fatal("%s/%s.%d: Key to delete \"%s\" not found!\n", + tree->module, MYNAME, __LINE__, key); + return 0; + } + + compare = tree->compare(key, node->key); + + if (compare < 0) { + deleted = avltree_delete_node(tree, key, &node->left, changed); + if (*changed) { + node->balance++; /* shift weight to right */ + switch(node->balance) { + case +1: + (*changed) = 0; /* stop rebalancing */ + case 0: + break; + case +2: + if (node->right->balance >= 0) + node = avltree_right_rotation(node); + else + node = avltree_right_left_rotation(node); + (*root) = node; + if (node->balance == -1) + (*changed) = 0; + break; + default: + /* should be impossible :-) */ + fatal(AVLTREE_INVALID_BALANCE); + } + } + } + else if (compare > 0) { + deleted = avltree_delete_node(tree, key, &node->right, changed); + if (*changed) { + node->balance--; /* shift weight to left */ + switch(node->balance) { + case -1: + (*changed) = 0; /* stop rebalancing */ + case 0: + break; + case -2: + if (node->left->balance <= 0) + node = avltree_left_rotation(node); + else + node = avltree_left_right_rotation(node); + (*root) = node; + if (node->balance == +1) + (*changed) = 0; + break; + default: + /* should be impossible :-) */ + fatal(AVLTREE_INVALID_BALANCE); + } + } + } + else { + if (node->left) { + if (node->right) { + const char *temp_key; + const void *temp_data; + avlnode_t *succ = node->right; + + while (succ->left) succ = succ->left; /* find successor */ + + temp_key = succ->key; /* swap contents */ + temp_data = succ->data; + succ->key = node->key; + succ->data = node->data; + node->key = temp_key; + node->data = temp_data; + + deleted = avltree_delete_node(tree, key, &node->right, changed); + + if (*changed) { + node->balance--; /* shift weight to left */ + switch(node->balance) { + case -1: + (*changed) = 0; /* stop rebalancing */ + case 0: + break; + case -2: + if (node->left->balance <= 0) + node = avltree_left_rotation(node); + else + node = avltree_left_right_rotation(node); + (*root) = node; + if (node->balance == +1) + (*changed) = 0; + break; + default: + /* should be impossible :-) */ + fatal(AVLTREE_INVALID_BALANCE); + } + } + return deleted; + } + else { /* only left branch */ + (*root) = node->left; + node->left = NULL; + } + } + else if (node->right) { /* only right branch */ + (*root) = node->right; + node->right = NULL; + } + else /* only a simple leaf */ + (*root) = NULL; + + avltree_node_free(tree, node); + tree->count--; + (*changed) = 1; + deleted = 1; + } + + return deleted; +} + + +static avlnode_t * +avltree_dupe_node(const avltree_t *tree, const avlnode_t *node) +{ + avlnode_t *res = xcalloc(1, sizeof(*res)); + + if (tree->options & AVLTREE_STATIC_KEYS) + res->key = node->key; + else + res->key = xstrdup(node->key); + + res->balance = node->balance; + if (node->left) + res->left = avltree_dupe_node(tree, node->left); + if (node->right) + res->right = avltree_dupe_node(tree, node->right); + + return res; +} + + +static int +avltree_strcmpr(const char *s1, const char *s2) +{ + return -(strcmp(s1, s2)); +} + + +static int +avltree_case_ignore_strcmpr(const char *s1, const char *s2) +{ + return -(case_ignore_strcmp(s1, s2)); +} + + +static avlnode_t * +avltree_find_next(const avltree_t *tree, avlnode_t *node, const char *key) +{ + avlnode_t *prev = NULL; + + if (key == NULL) { + if ((node = tree->root)) { + while (node->left) + node = node->left; + } + return node; + } + + while (node) { + int compare = tree->compare(key, node->key); + + if (compare < 0) { + prev = node; + node = node->left; + } + else if (compare > 0) + node = node->right; + else { + if ((node = node->right)) + while (node->left) node = node->left; + else + node = prev; + return node; + } + } + /* The previous node was deleted and we could not find it. */ + return prev; +} + + +/* + Save [key] for a possible delete before next op. Now we have no problem with: + + curr = NULL; + while ((curr = avtree_next(tree, curr, NULL))) { + avltree_delete(tree, curr); + } + */ +static void +avltree_save_key(avltree_t *tree, const char *key) +{ + if (tree->options & AVLTREE_STATIC_KEYS) + tree->key = key; + else { + if (key == NULL) { + if (tree->key_sz) { + xfree((char *)tree->key); + tree->key = NULL; + tree->key_sz = 0; + } + } + else { + int n, n8; + + n = strlen(key) + 1; + n8 = ((n + 7) / 8) * 8; + + if (n8 > tree->key_sz) { + if (tree->key_sz == 0) + tree->key = xmalloc(n8); + else + tree->key = xrealloc((char *)tree->key, n8); + tree->key_sz = n8; + } + strncpy((char *)tree->key, key, n); + } + } +} diff --git a/gpsbabel/avltree.h b/gpsbabel/avltree.h new file mode 100644 index 000000000..d8c9ddb4e --- /dev/null +++ b/gpsbabel/avltree.h @@ -0,0 +1,94 @@ +/* + + AVL tree implementation. + + Copyright (C) 2008 Olaf Klein, o.b.klein@gpsbabel.org + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA + +*/ + +#ifndef AVLTREE_H_INCLUDED +#define AVLTREE_H_INCLUDED + +#include "defs.h" +#include +#include + +typedef int (*avltree_compare_cb) (const char *, const char *); + +typedef struct avltree_s +{ +#ifdef MEM_DEBUG + const int magic; +#endif + struct avlnode_s *root; + const char *module; + int count; /* number of items in tree */ + int options; + const char *key; + int key_sz; + avltree_compare_cb compare; +} avltree_t; + +typedef struct avlnode_s { + int balance; + const char *key; + const void *data; + struct avlnode_s *left; + struct avlnode_s *right; +} avlnode_t; + +/* options for avltree_init */ + +#define AVLTREE_ASCENDING 0 /* default */ +#define AVLTREE_DESCENDING 1 +#define AVLTREE_CASE_SENSITIVE 0 /* default */ +#define AVLTREE_NON_CASE_SENSITIVE 2 +#define AVLTREE_STATIC_KEYS 128 +#define AVLTREE_PARANOIAC 256 /* STOP on "duplicate key" (insert) or on "not found" (delete) */ + +/* Allocate and initialize an AVL Tree */ +avltree_t *avltree_init(const int options, const char *module); + +/* Destroy an AVL Tree */ +void avltree_done(avltree_t *tree); + +/* Get number of items in tree */ +int avltree_count(const avltree_t *tree); + +/* Delete item with key [key] */ +int avltree_delete(avltree_t *tree, const char *key); + +/* Duplicate an existing tree */ +avltree_t *avltree_dupe(const avltree_t *tree, const char *module); + +/* Find key [key] in tree */ +int avltree_find(const avltree_t *tree, const char *key, const void **data); + +/* Get the first (the MIN-) entry of the tree */ +const char *avltree_first(const avltree_t *tree, const void **data); + +/* Get the current height of the tree */ +int avltree_height(const avltree_t *tree); + +/* Insert key [key] and [data] into tree */ +int avltree_insert(avltree_t *tree, const char *key, const void *data); + +/* Get the next (the entry above [key]) */ +const char *avltree_next(const avltree_t *tree, const char *key, const void **data); + + +#endif /* AVLTREE_H_INCLUDED */ -- 2.30.2